package com.jia.jianzhiOffer;

import java.util.LinkedList;

/**
 * @program: Leetcode
 * @description:
 * @author: STU756
 * @create: 2020-08-05 00:49
 */
public class Pro59_2 {
    private int size;
    private LinkedList<Integer> queue = new LinkedList<Integer>();
    private LinkedList<Integer> max = new LinkedList<Integer>();
    public Pro59_2() {
        this.size = 0;
    }

    public int max_value() {
        return isEmpty()? -1 : max.peek();
    }

    public void push_back(int value) {
        queue.offer(value);
        while(!max.isEmpty() && value > max.peekLast()) {
            max.pollLast();
        }
        max.offer(value);
        ++size;
    }

    public int pop_front() {
        if(isEmpty()) { return -1; }
        int val = queue.pop();
        if(val == max.peek()) {
            max.pop();
        }
        --size;
        return val;
    }
    public boolean isEmpty(){
        return size == 0;
    }


    public static void main(String[] args) {
        Pro59_2 pro59_2 = new Pro59_2();
        pro59_2.push_back(1);
        pro59_2.push_back(2);
        System.out.println(pro59_2.max_value());
        System.out.println(pro59_2.pop_front());
        System.out.println(pro59_2.pop_front());
    }
}
